package class19;

/**
 * @author YZY
 * @since 2022/8/18 12:33
 * <a href="https://www.acwing.com/problem/content/description/2/">2. 01背包问题</a>
 */
public class Code01_Knapsack {

    // 暴力递归
    public static int knapsack1(int[] w, int[] v, int bag) {
        return process1(w, v, bag, 0);
    }

    private static int process1(int[] w, int[] v, int bag, int index) {
        if (index == w.length) {
            return 0;
        }
        int no = process1(w, v, bag, index + 1);
        if (bag < w[index]) {
            return Math.max(no, 0);
        }
        int yes = process1(w, v, bag - w[index], index + 1) + v[index];
        return Math.max(no, yes);
    }

    // 记忆化搜索 + 逻辑小改
    public static int knapsack2(int[] w, int[] v, int bag) {
        int[][] dp = new int[w.length + 1][bag + 1];
        return process2(w, v, dp, bag, 0);
    }

    private static int process2(int[] w, int[] v, int[][] dp, int bag, int index) {
        if (dp[index][bag] != 0) {
            return dp[index][bag];
        }
        if (index == w.length) {
            return 0;
        }
        int no = process2(w, v, dp, bag, index + 1);
        int yes = bag < w[index] ? 0 : process2(w, v, dp, bag - w[index], index + 1) + v[index];
        return dp[index][bag] = Math.max(no, yes);
    }

    // 动态规划
    public static int knapsack3(int[] w, int[] v, int bag) {
        int[][] dp = new int[w.length + 1][bag + 1];
        // 根据暴力递归可以知道，index == W.length那一行都为0
        // dp[w.length][...] = 0;
        // 每index行的数据，都是从index+1拿到的，那么就用自底向上来遍历
        for (int index = w.length - 1; index >= 0; --index) {
            // index从W.length-1开始是因为W.length那一行都为0，无需在去重复遍历一遍
            // 然后从左往右或者从右往左遍历都可以
            for (int rest = 0; rest <= bag; ++rest) {
                // 接着只要看暴力递归中的过程，推出状态转移方程就行
                int no = dp[index + 1][rest];
                int yes = rest < w[index] ? 0 : v[index] + dp[index + 1][rest - w[index]];
                dp[index][rest] = Math.max(no, yes);
            }
        }
        return dp[0][bag];
    }

    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7, 3, 1, 7};
        int[] values = {5, 6, 3, 19, 12, 4, 2};
        int bag = 15;
        System.out.println(knapsack1(weights, values, bag));
        System.out.println(knapsack2(weights, values, bag));
        System.out.println(knapsack3(weights, values, bag));
    }

}
